/*
 * @author	Mabel Xu
 */

import java.util.ArrayList;
import info.gridworld.grid.AbstractGrid;
import info.gridworld.grid.Location;

public class SparseBoundedGrid<E> extends AbstractGrid<E>
{
	private SparseGridNode[] rows;
	private int maxNodes;
	
	public SparseBoundedGrid(int r, int c)
	{
		if (r <= 0)
            throw new IllegalArgumentException("rows <= 0");
        if (c <= 0)
            throw new IllegalArgumentException("cols <= 0");
		rows = new SparseGridNode[r];
		maxNodes = c;
	}
	
	public int getNumRows()
	{
		return rows.length;
	}
	
	public int getNumCols()
	{
		return maxNodes;
	}
	
	public boolean isValid(Location l)
    {
        return 0 <= l.getRow() && l.getRow() < this.getNumRows()
                && 0 <= l.getCol() && l.getCol() < this.getNumCols();
    }
	
	public ArrayList<Location> getOccupiedLocations()
	{
		ArrayList<Location> locs = new ArrayList<Location>();
	
		for (int i = 0; i < rows.length; i++)
		{
			SparseGridNode current = rows[i];
			while (current != null)
			{
				if (current.getOccupant() != null)
					locs.add(new Location(current.getCol(), i));
				current = current.getNext();
			}
		}
	    
	    return locs;
	}
	
	public E get(Location l)
	{
		if (!this.isValid(l))
			throw new IllegalArgumentException("Location " + l
					+ " is not valid");
		SparseGridNode current = rows[l.getRow()];
		while (current != null && current.getCol() != l.getCol())
			current = current.getNext();
		
		if (current == null)
			return null;
		else
			return (E) current.getOccupant();
	}
	
	public E put(Location l, E o)
	{
		if (!this.isValid(l))
			throw new IllegalArgumentException("Location " + l
					+ " is not valid");
		if (o == null)
		    throw new NullPointerException("obj == null");
		
		E oldOccupant = this.get(l);
		
		if (this.get(l) != null)
		{
			SparseGridNode current = rows[l.getRow()];
			while (current.getCol() != l.getCol())
				current = current.getNext();
			current.setOccupant(o);
		}
		else if (rows[l.getRow()] == null)
		{
			rows[l.getRow()] = new SparseGridNode(o, l.getCol(), null);
		}
		else if (l.getCol() < rows[l.getRow()].getCol())
		{
			rows[l.getRow()] = new SparseGridNode(o, l.getCol(), rows[l.getRow()]);
		}
		else
		{
			SparseGridNode ahead = rows[l.getRow()];
			SparseGridNode behind = ahead.getNext();
			while (behind.getCol() < l.getCol())
			{
				ahead = ahead.getNext();
				behind = behind.getNext();
			}
			ahead.setNext(new SparseGridNode(o, l.getCol(), behind));
		}
		
		return oldOccupant;
	}
	
	public E remove(Location l)
	{
		if (!this.isValid(l))
			throw new IllegalArgumentException("Location " + l
					+ " is not valid");
        
		E r = this.get(l);
		
		if (this.get(l) == null)
		{
			// Location l already empty, so do nothing;
		}
		else if (l.getCol() == 0)
		{
			rows[l.getRow()] = rows[l.getRow()].getNext();
		}
		else
		{
			SparseGridNode ahead = rows[l.getRow()];
			SparseGridNode behind = ahead.getNext().getNext();
			while (ahead.getNext().getCol() != l.getCol())
			{
				ahead = ahead.getNext();
				behind = behind.getNext();
			}
			ahead.getNext().setNext(null);
			ahead.setNext(behind);			
		}
        
		return r;
	}
}
